import java.util.*;

public class Test {
}
class Solution1 {
    public long maxSum(List<Integer> nums, int m, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        long ans = 0;
        long cur = 0;
        for(int i=0; i<nums.size(); i++){
            cur += nums.get(i);
            map.put(nums.get(i),map.getOrDefault(nums.get(i),0)+1);
            if(i >= k-1){
                if(map.size()>=m){//只有满足m时，得到ans
                    ans = Math.max(ans,cur);
                }
                //这个子数组满足/不满足条件，都要更换
                int out = nums.get(i-k+1);//要删除的数
                int val = map.get(out);
                if(val==1){
                    map.remove(out);
                }else{
                    map.put(out,val-1);
                }
                cur -= out;
            }

        }
        return ans;
    }
}
class Solution {
    private static final long MOD = (long) 1e9 + 7;
    /**
     TreeMap中存储是有顺序的！！！
     TreeMap使用Map.entrySet()是从小到大输出的！！！
     HashMap使用Map.entrySet()是随机输出的！！！
     */
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        int[] cnt = new int[26];
        for(int i=0; i<s.length(); i++){
            cnt[s.charAt(i)-'a']++;
        }
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int x : cnt){
            if(x > 0)
                map.put(-x,map.getOrDefault(-x,0)+1);
            //<出现次数,出现次数相同的字母有几个>
        }
        long ans = 1;
        for(Map.Entry<Integer,Integer> x : map.entrySet()){
            int i = -x.getKey();//出现次数
            int j = x.getValue();//出现次数相同的字母有几个
            if(j >= k)
                return (int)(ans*pow(i,k)%MOD*comb(j,k)%MOD);
            ans = ans * pow(i,j) % MOD;
            k -= j;
        }
        return 0;
    }
    long pow(long x, int n){//快速幂算法
        long res = 1;
        while(n != 0){
            if(n%2 != 0){
                res = res*x%MOD;
            }
            x = x*x%MOD;
            n/=2;
        }
        return res;
    }
    long comb(long n, int k){//数学中的组合排序算法
        long res = n;
        for(int i=2; i<=k; i++){
            res = res*(--n)/i;
        }
        return res%MOD;
    }
}
class Solution2 {
    public int triangleNumber(int[] nums) {
        int ans = 0;
        Arrays.sort(nums);
        int n = nums.length;
        for(int i=n-1; i>=2; i--){
            int left = 0;
            int right = i-1;
            while(left < right){
                if(nums[left]+nums[right]<=nums[i])
                    left++;
                else{
                    ans = ans + right-left;
                    right--;
                }
            }
        }
        return ans;
    }
}